1. Field of the Invention
The present invention generally relates to computer networks. More particularly, the invention relates to electronic switches through which communications pass from one point in a network to another. Still more particularly, the invention relates to load balancing in a switch-based fabric.
2. Background Information
Initially, computers were most typically used in a standalone manner. It is now commonplace for computers and other types of computer-related and electronic devices to communicate with each other over a network. The ability for computers to communicate with one another has lead to the creation of networks ranging from small networks comprising two or three computers to vast networks comprising hundreds or even thousands of computers. Networks can be set up to provide a wide assortment of capabilities. For example, networks of computers may permit each computer to share a centralized mass storage device or printer. Further, networks enable electronic mail and numerous other types of services. Generally, a network's infrastructure comprises switches, routers, hubs and the like to coordinate the effective and efficient transfer of data and commands from one point on the network to another.
Networks often comprise a “fabric” of interconnected switches which are devices that route data packets from a source port to a destination port. FIG. 1 exemplifies a switch fabric having five switches 20, 22, 24, 26, and 28. The switches 20-28 are interconnected by links 30-38, as shown. One or more devices can be connected to any of the switches. In FIG. 1, four devices 40 are connected to switch 20 and two devices 42 connect to switch 24. The devices may be any desirable types of devices such as servers and storage devices.
A device 40 connected to switch 20 may need to send a data packet to a device 42 connected to switch 24. The packet can be routed from switch 20 to switch 24 via one of two paths in the exemplary architecture of FIG. 1. One path comprises switches 20-22-24 and the other path comprises switches 20-28-26-24. In many networks, the path that will be used between pairs of switches is determined a priori during system initialization or when the fabric configuration changes such as the addition or removal of a switch. Various path selection algorithms have been suggested and used. One such conventional path selection algorithm is often referred to as the “shortest path” algorithm. According to this algorithm, the shortest path is selected to be the path for routing packets between switches. The shortest path takes into account the bandwidth of the various links interconnecting the switches.
Referring still to FIG. 1, a “cost” value is assigned to each link. The numbers shown in parentheses adjacent each link represents the cost of each link. The cost values are generally arbitrary in magnitude, but correlate with a system criteria such as the inverse of the bandwidth of the links. That is, higher bandwidth links have lower costs. For example, links 30 and 32 may have the same bandwidth (e.g., 1 gigabits per second (“gbps”)) and may be assigned a cost value of 1000. Links 34, 36, and 38 may have twice the bandwidth of links 30 and 32 (2 gbps) and accordingly may be assigned cost values of 500 (one-half of the cost of links 30 and 32). The shortest path represents the path with the lowest total cost. The total cost of the path is the sum of the costs associated with the links comprising the path. In the example of FIG. 1, the 20-22-24 path has a total cost of 2000, while the total cost of the 20-28-26-24 path is 1500. As the lowest cost path, the 20-28-26-24 path will be selected to be the path used for routing data packets between devices 40 and 42. It should be understood that the cost values may be related to other system criteria besides bandwidth. Examples include the delay in crossing a link and a monetary cost an entity might charge for the ISL.
A complication to the lowest cost path selection algorithm is introduced when “trunks” are implemented in a switching fabric. For additional information regarding trunking, please refer to U.S. Pat. No. 09/872,412, filed Jun. 1, 2001, entitled “Link Trunking and Measuring Link Latency in Fibre Channel Fabric,” by David C. Banks, Kreg A. Martin, Shunjia Yu, Jieming Zhu and Kevan K. Kwong, incorporated herein by reference. For example, FIG. 2 repeats the fabric architecture of FIG. 1, but also includes a trunk 48 interconnecting switches 20 and 22. In general, a trunk comprises a logical collection of two or more links. In FIG. 2, trunk 48 comprises four links. Although the trunk is actually four separate parallel links, the trunk appears as one logical “pipe” for data to flow between switches. Hardware (not specifically shown) in switches 20 and 22 selects one of the various links comprising the pipe when sending a data packet across the trunk, thereby alleviating the higher level logic in the switch from controlling the operation of the trunk.
Because the links comprising the trunk can be used simultaneously to send data packets, the trunk effectively has a bandwidth that is greater than the bandwidth of the links comprising the trunk. In FIG. 2, if the bandwidth of each link comprising trunk 48 is the same as the bandwidth of separate link 30 (i.e., 1 gbps), the effective bandwidth of trunk 48 with four 1 gbps links is 4 gbps. In the context of each path having a cost associated with it, the system might assign trunk 48 a cost of one-fourth the cost of link 30, which would be a cost of 250. Then, the lowest cost path from devices 40 to devices 42 would be the 1250 cost path comprising switches 20-22-24 and including trunk 48 between switches 20 and 22.
In some situations, this will be a satisfactory implementation. However, this implementation may be less than satisfactory in other situations. Because traffic from devices 40 will be routed from switch 20 to switch 22 through trunk 48 to the exclusion of link 30, trunk 48 will carry all of the traffic and parallel link 30 will carry no traffic and thus be underutilized. This is acceptable if the bandwidth of the data does not exceed the capacity of trunk 48. If the data does exceed the bandwidth of the trunk, then performance is reduced despite link 30 being available to carry traffic, but not being used in that regard.
Referring still to FIG. 2, devices 40 and 42 connect to ports 46 and 44, respectively, contained in their associated switches 20 and 24. The speed of the links connecting devices 40, 42 to their ports 46, 44 may vary from device to device. Some devices, for example, may connect via a 1 gbps link, while other devices connect via 2 gbps links. The conventional shortest path selection algorithm typically does not take into account the speed of the peripheral links connecting the peripheral devices to the switches when assigning the source ports (e.g., ports 46) to the paths determined to be shortest, thereby possibly resulting in less than optimal path assignments.
Accordingly, a solution to these problems is needed. Such a solution preferably would efficiently merge together tank implementations in the face of a network fabric based on a shortest path selection algorithm and take into account peripheral link speeds.